\documentclass[12pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\author{Bendavid Olivier,  Pallet David, Haderer Nicolas}
\title{Linéarisation de machines à états}

\begin{document}

\maketitle
\newpage
\tableofcontents
\newpage

\section{Sujet}
\paragraph{Manipulation de modèles UML : linéarisation de machines à états
Vous implémenterez (par exemple en Kermeta) une transformation de modèle qui à partir d'une machine à état UML M, produit une autre 
machine à état de comportement équivalent à M mais dans laquelle il n'y a plus ni états composites ni états orthogonaux. Vous 
remettrez également un court rapport explicatif. }

\section{Définition}
\paragraph{Dans cette partie nous présenterons les différentes définitions relatives aux projets.}

\subsection{Machine à états}
\paragraph{Un automate fini (on dit parfois machine à états finie), en anglais ''finite state automaton'' ou ''finite state machine'' (FSA, 
FSM), est une machine abstraite utilisée en théorie de la calculabilité et dans l'étude des langages formels. \\\\
C'est un outil fondamental en Informatique, où il intervient notamment en compilation des langages informatiques (procédé permettant de passer 
d'un langage de haut niveau en langage machine binaire).\\\\
Un automate est constitué d'états et de transitions. Son comportement est dirigé par un mot fourni en entrée : l'automate passe 
d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. L'automate est dit " fini " car il possède un 
nombre fini d'états distincts : il ne dispose donc que d'une mémoire bornée.\\\\
Un automate fini forme un graphe orienté étiqueté, dont les états sont les sommets et les transitions les arêtes étiquetées.}

\subsection{État composite}
\paragraph{Un état simple ne possède pas de sous-structure mais uniquement, le cas échéant, un jeu de transitions internes. Un état 
composite est un état décomposé en régions contenant chacune un ou plusieurs sous-états.\\\\
Quand un état composite comporte plus d’une région, il est qualifié d’état orthogonal. Lorsqu’un état orthogonal est actif, un 
sous-état direct de chaque région est simultanément actif, il y a donc concurrence. Un état composite ne 
comportant qu’une région est qualifié d’état non orthogonal.\\\\
Implicitement, tout diagramme d’états-transitions est contenu dans un état externe qui n’est usuellement pas représenté. Cela 
apporte une plus grande homogénéité dans la description : tout diagramme d’états-transitions est implicitement un état composite.\\\\
Exemple d’état composite: }

\begin{center}
\includegraphics[scale=0.4]{pictures/exEtatComposite.png} 
\end{center}

\subsection{État orthogonal}
\paragraph{Les diagrammes d’états-transitions permettent de décrire efficacement les mécanismes concurrents grâce à l’utilisation 
d’états orthogonaux. \\\\
Un état orthogonal est un état composite comportant plus d’une région, chaque région représentant un flot 
d’exécution. Graphiquement, dans un état orthogonal, les différentes régions sont séparées par un trait horizontal en pointillé 
allant du bord gauche au bord droit de l’état composite.\\\\
Chaque région peut posséder un état initial et final. Une transition qui atteint la bordure d’un état composite orthogonal est 
équivalente à une transition qui atteint les états initiaux de toutes ses régions concurrentes.
Toutes les régions concurrentes d’un état composite orthogonal doivent atteindre leur état final pour que l’état composite soit 
considéré comme terminé.\\\\
La figure suivante illustre l’utilisation d’un état composite orthogonal pour modéliser le fait que la préparation de la boisson d’un 
distributeur de boisson se fait en parallèle au rendu de la monaie: }

\begin{center}
\includegraphics[scale=0.3]{pictures/exConcurrenceEtat.png} 
\end{center}

\section{Présentation de l'exemple utilisé}
\paragraph{}

\section{Méta-modèle}
\paragraph{Dans cette partie, nous allons vous présenter un extrait du méta-modèle UML des machines à états ainsi que le nouveau méta-modèle, celui représentant les machines à états après linéarisation.}
\subsection{Extrait du méta-modèle UML des machines à états}
\paragraph{Commençons tout d'abord par rappeler (un extrait) le méta-modèle UML des machines à états: }

\begin{center}
\includegraphics[scale=0.6]{pictures/machineEtats.png} 
\end{center}

\paragraph{Une machine à états est un comportement. A ce titre, elle est reliée à un contexte (un classifieur à comportement) qui dans notre cas sera une classe (ce pourrait être aussi un cas d'utilisation par exemple).\\\\ 
La machine à  états peut accéder à toutes les propriétés et
associations de son contexte. Une machine à  états est composée de régions. \\\\
Une région se compose de sommets (Vertex) et de transitions. Vertex est une classe abstraite factorisant les  états et les pseudo- états. Un vertex est lié à ses transitions sortantes (outgoing) et entrantes (incoming).\\\\
 Les pseudo-états peuvent être de plusieurs sortes (jonction, branchement, etc). La métaclasse State permet de représenter les  états de la machine à  états (graphiquement représentés par des
rectangles à coins arrondis). FinalState est la métaclasse qui permet de représenter les  états finaux d'une machine à  états (graphiquement représentés par un disque noir entouré d'un cercle). Chaque transition relie 2 Vertex (Source et Target). Une transition se compose d'une
éventuelle garde (sous forme d'une contrainte) et d'un ensemble de déclencheurs ou gâchettes (trigger). Chaque déclencheur est lié à l'événement permettant de le déclencher. }

\subsection{Extrait du méta-modèle UML des machines à états linéarisées}
\paragraph{Dans cette partie, nous allons maintenant vous présenter l'extrait du nouveau méta-modèle. Il s'agit du méta-modèle de la partie précédente mais avec différentes modifications permettant ainsi de représenter les machines à états linéarisées. Ces modifications sont les suivantes: }
\begin{itemize}
	\item modification de la cardinalité de la collection entre les classes StateMachine et Region, de sorte à ce qu'une machine à état ne possède qu'une seule région (une ''MainRegion'')
	\item suppression de la collection entre les classe ''Region'' et ''Transition''
\end{itemize}

\begin{center}
\includegraphics[scale=0.6]{pictures/machineEtatsLineaire.png}  
\end{center}

\paragraph{Ceci étant, une machine à état ne peut donc pas avoir plusieurs régions et ces états ne peuvent pas non plus en avoir. Nous avons donc une machine à états possédant une région principale et des états avec leurs transitions, un état initial et un état final.}


\section{Présentation du programme}
\subsection{Le parcours}
\paragraph{Le parcours s'effectue en récuperant les transitions du modèle a transformer, il débute par l'état initial et se termine 
après avoir parcouru toutes les transitions.}

\subsection{Les transformations}
\paragraph{Lorsque la cible d'une transition est un état composite, état possédant une région, ou un état orthogonal, état 
possédant plus d'une région, on ajoute un nouvel état et une transition le reliant a l'état source, on ajoute ensuite la ou les 
transitions entre le nouvel état créé et l'état suivant l'état initial interne au composite, on ajoute les différents états interne 
du composite en suivant les transitions. Lorsqu'on trouve un état Final on ajoute un nouvel état  et la ou les transitions reliant 
le ou lés états précedant l'état final, puis on relie ce nouvel état aux cible des transitions sortantes du composite.
}
\paragraph{L'ensemble des transformations pour retirer un composite consiste donc en l'ajout d'un état supplémentaire de part et 
d'autres de l'état composite et de remplacer les états initiaux et finaux par nos deux états nouvellement créés. Les transitions 
sont conservées car on relie les transitions entrantes et sortantes du composite a nos nouveaux états ajoutés.}


\begin{center}
\includegraphics[scale=0.3]{pictures/ExempleComposite.png} 
\includegraphics[scale=0.3]{pictures/ExempleCompositeLinearise.png} 
\end{center}

\paragraph{Pour les transformations des états orthogonaux, c'est le m\^{e}me principe que pour un état composite, sauf qu'on 
l'applique a chacune des régions de l'état orthogonal.}

\begin{center}
\includegraphics[scale=0.3]{pictures/ExempleOrthogonal.png} 
\includegraphics[scale=0.3]{pictures/ExempleOrthogonalLinearise.png} 
\end{center}

\subsection{Utilisation}
\paragraph{}

\section{Conclusion}

\end{document}